package cn.xaut.查找表;

import java.util.HashMap;
import java.util.Map;

public class demo447 {

    private int dis(int[] pa, int[] pb) {

        return (int) (Math.pow((pa[0] - pb[0]), 2) + Math.pow((pa[1] - pb[1]), 2));
    }
    
    // 时间复杂度：O(N^2)
    public int numberOfBoomerangs2(int[][] points) {

        int len = points.length;

        if (len < 3)
            return 0;

        int count = 0;
        for (int i = 0; i < len; i++) {
            Map<Integer, Integer> map = new HashMap<>();
            for (int j = 0; j < len; j++) {
                if (j == i)
                    continue;
                // 计算距离时不进行开根运算，以保证精度
                int dis = dis(points[i], points[j]);
                map.put(dis, map.getOrDefault(dis, 0) + 1);
            }

            for (int key : map.keySet()) 
                count += map.get(key) * (map.get(key) - 1);
        }

        return count;
    }

    private double getDistance(int[] p1, int[] p2) {

        return Math.sqrt(Math.pow(p1[0] - p2[0], 2) + Math.pow(p1[1] - p2[1], 2));
    }

    private boolean isBoomerangs(int[] p1, int[] p2, int[] p3) {

        assert p1.length == 2 && p2.length == 2 && p3.length == 2;

        double dis1 = getDistance(p1, p2);
        double dis2 = getDistance(p1, p3);
        double dis3 = getDistance(p2, p3);

        return dis1 == dis2 || dis1 == dis3 || dis2 == dis3;
    }

    // 时间复杂度：O(N^3)
    public int numberOfBoomerangs(int[][] points) {

        int len = points.length;

        if (len < 3)
            return 0;

        int count = 0;
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                for (int k = j + 1; k < len; k++) {
                    if (isBoomerangs(points[i], points[j], points[k]))
                        count += 2;
                }
            }
        }

        return count;
    }

    public static void main(String[] args) {

        System.out.println(new demo447().numberOfBoomerangs2(new int[][]{{0, 0}, {1, 0}, {2, 0}}));//2
        System.out.println(new demo447().numberOfBoomerangs2(new int[][]{{1, 1}, {2, 2}, {3, 3}}));//2
        System.out.println(new demo447().numberOfBoomerangs2(new int[][]{{1, 1}}));//0
        System.out.println(new demo447().numberOfBoomerangs2(new int[][]{{0, 0}, {1, 0}, {-1, 0}, {0, 1}, {0, -1}}));//20
        System.out.println(Math.pow(2, 31));
    }
}
